package Leetcode.lc239;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/***
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回 滑动窗口中的最大值 。 HARD
 */
public class Sloution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //单调队列,使用双端队列,存的是索引
        Deque<Integer> deque = new LinkedList<>();
        //存在的窗口数量
        int[] res=new int[nums.length-k+1];
        int resindex=0;
        //开始遍历，获得最大值
        for(int i=0;i<nums.length;i++){
            //去除过期元素，0，1，2，3，k=3，i=3的时候要滑动窗口，所以移除i-k，0索引的元素
            if(!deque.isEmpty() && deque.peek()==i-k){
                deque.remove();
            }
            //清除队内元素小于新插入的元素，维护单调递减,从队尾加
            while(!deque.isEmpty() && nums[i]>=nums[deque.peekLast()]){
                deque.removeLast();
            }
            //新元素入队
            deque.offer(i);
            //获取最大的元素（当窗口元素被填满）=k-1刚好填满，往下的状态均满，所以>=
            if(i>=k-1){
                //单调递减，最大索引为单调队列的队首
                res[resindex++]=nums[deque.peek()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Sloution sloution = new Sloution();
        int[] test={1,3,-1,-3,5,3,6,7};
        int k=3;
        int[] ints = sloution.maxSlidingWindow(test, k);

    }
}
